package leetcode;

/**
 * 给你一个整数数组 arr 和一个整数 k。
 * 
 * 首先，我们要对该数组进行修改，即把原数组 arr 重复 k 次。
 * 
 * 举个例子，如果 arr = [1, 2] 且 k = 3，那么修改后的数组就是 [1, 2, 1, 2, 1, 2]。
 * 
 * 然后，请你返回修改后的数组中的最大的子数组之和。
 * 
 * 注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
 * 
 * 由于 结果可能会很大，所以需要 模（mod） 10^9 + 7 后再返回。 
 *
 * 参考https://leetcode-cn.com/problems/k-concatenation-maximum-sum/solution/java-kadanesuan-fa-yu-jie-ti-si-lu-by-zdxiq125/
 */
public class Solution1191_leetcode {// Kadane算法
	public int kConcatenationMaxSum(int[] arr, int k) {
		if (arr == null || arr.length == 0)
			return 0;
		long maxOfEnd = arr[0] > 0 ? arr[0] : 0L, maxSoFar = maxOfEnd, sum = arr[0];
		for (int i = 1; i < Math.min(k, 2) * arr.length; i++) {
			maxOfEnd = Math.max(maxOfEnd + arr[i % arr.length], arr[i % arr.length]);
			maxSoFar = Math.max(maxOfEnd, maxSoFar);
			if (i < arr.length)
				sum += arr[i];
		}
		while (sum > 0 && --k >= 2)
			maxSoFar = (maxSoFar + sum) % 1000000007;
		return (int) maxSoFar;
	}
}
